import com.sun.source.tree.Tree;

import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-10-15
 * Time: 10:42
 */
public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    //1.前序遍历
        //递归
    public void preOrder(TreeNode root){
        if (root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public List<Character> preOrderTraversal(TreeNode root){
        List<Character> list = new ArrayList<>();
        if (root == null) return list;
        list.add(root.val);
        list.addAll(preOrderTraversal(root.left));
        list.addAll(preOrderTraversal(root.right));
        return list;
    }
        //非递归
    public void preOrder1(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.empty()){
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            cur = node.right;
        }
        System.out.println();
    }
        //非递归优化
    public void new_preOrder1(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode node = null;
        while (cur != null || !stack.empty()){
            while (cur != null) {
                if (cur.right != null) stack.push(cur.right);
                else stack.push(null);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            node = stack.pop();
            cur = node;
        }
        System.out.println();
    }

    //用数组储存
    private char[] arr1 = new char[100];
    private int i1;
    public char[] preOrder2(TreeNode root){
        if (root == null) return arr1;
        arr1[i1] = root.val;
        if (root.left != null) arr1[2 * i1 + 1] = root.left.val;
        if (root.right != null) arr1[2 * i1 + 2] = root.right.val;
        i1++;
        preOrder2(root.left);
        preOrder2(root.right);
        return arr1;
    }
    //2.中序遍历
        //递归
    public void inOrder(TreeNode root){
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    public List<Character> inOrderTraversal(TreeNode root){
        List<Character> list = new ArrayList<>();
        if (root == null) return list;
        list.addAll(inOrderTraversal(root.left));
        list.add(root.val);
        list.addAll(inOrderTraversal(root.right));
        return list;
    }
        //非递归
    public void inOrder1(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.empty()){
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            cur = node.right;
        }
        System.out.println();
    }
    //用数组储存
    private char[] arr2 = new char[100];
    private int i2;
    public char[] inOrder2(TreeNode root){
        if (root == null) return arr2;
        inOrder2(root.left);
        arr2[i2] = root.val;
        if (root.left != null) arr2[2 * i2 + 1] = root.left.val;
        if (root.right != null) arr2[2 * i2 + 2] = root.right.val;
        i2++;
        inOrder2(root.right);
        return arr2;
    }
    //3.后序遍历
        //递归
    public void postOrder(TreeNode root){
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    public List<Character> postOrderTraversal(TreeNode root){
        List<Character> list = new ArrayList<>();
        if (root == null) return list;
        list.addAll(postOrderTraversal(root.left));
        list.addAll(postOrderTraversal(root.right));
        list.add(root.val);
        return list;
    }
        //非递归
    public void postOrder1(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null || !stack.empty()){
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.peek();

            if (node.right == null || node.right == prev){
                System.out.print(node.val + " ");
                prev = node;
                stack.pop();
            }else{
                cur = node.right;
            }
        }
        System.out.println();
    }

    //用数组储存
    private char[] arr3 = new char[100];
    private int i3;
    public char[] postOrder2(TreeNode root){
        if (root == null) return arr3;
        postOrder2(root.left);
        postOrder2(root.right);
        arr3[i3] = root.val;
        if (root.left != null) arr3[2 * i3 + 1] = root.left.val;
        if (root.right != null) arr3[2 * i3 + 2] = root.right.val;
        i3++;
        return arr3;
    }
    //4.获取树的节点个数
    //子问题方法
    public int size(TreeNode root){
        if (root == null) return 0;
        return  size(root.left) + size(root.right) + 1;
    }
    //递归计数
    private int usedSize;
    public int size1(TreeNode root){
        if (root == null) return 0;
        usedSize++;
        size1(root.left);
        size1(root.right);
        return usedSize;
    }
    //5.获取叶子结点的个数
    //遍历树，当root左边和右边都是空的时候，就是叶子。
    private int leftNodeSize;
    public int getLeafNodeCount(TreeNode root){
        if (root == null) return 0;
        if (root.right == null && root.left == null) leftNodeSize++;
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return leftNodeSize;
    }
    //子问题
    public int getLeafNodeCount1(TreeNode root){
        if (root == null){
            return 0;
        }else if (root.right == null && root.left == null){
            return 1;
        }
        return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);
    }
    //6.获取第k层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if (root == null) return 0;
        if (k == 0) return 1;
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }
    //7.获取二叉树的高度
    public int getHeight(TreeNode root){
        if (root == null) return 0;
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
    //8.获取二叉树的深度
    public int getDepth(TreeNode root){
        return getHeight(root) - 1;
    }
    //9.检测值为value的元素是否存在
    public TreeNode find(TreeNode root, char value){
        if (root == null) return null;
        if (root.val == value) return root;
        TreeNode left = find(root.left,value);
        TreeNode right= find(root.right,value);
        return left == null ? right : left;
    }
    //10.层序遍历
    public void levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    public List<List<Character>> levelOrder1(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Character>> listAll = new ArrayList<>();
        if (root == null) return listAll;
        queue.offer(root);
        while (!queue.isEmpty()){
            int count = queue.size();
            List<Character> list = new ArrayList<>();
            for (int i = 0; i < count; i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            listAll.add(list);
        }
        return listAll;
    }
    public List<Character> rightLook(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Character> listRight = new ArrayList<>();
        if (root == null) return listRight;
        queue.offer(root);
        while (!queue.isEmpty()){
            int count = queue.size();
            List<Character> list = new ArrayList<>();
            for (int i = 0; i < count; i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            listRight.add(list.get(list.size() - 1));
        }
        return listRight;
    }
    //数组存储(仅限于完全二叉树)
    private char[] arr = new char[100];
    private int i;
    public char[] levelOrder2(TreeNode root){
        if (root == null) return arr;
        i = findPos(arr, root.val);
        arr[i] = root.val;
        if (root.left != null) arr[2 * i + 1] = root.left.val;
        if (root.right != null) arr[2 * i + 2] = root.right.val;
        levelOrder2(root.left);
        levelOrder2(root.right);
        return arr;
    }
    private int findPos(char[] arr, char key){
        for (int i = 0; i < arr.length; i++){
            if (arr[i] == key) return i;
        }
        return 0;
    }
    //11.判断是否为完全二叉树
    public boolean isCompleteTree(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return false;
        queue.offer(root);
        TreeNode node = queue.poll();
        while ( node != null){
            queue.offer(node.left);
            queue.offer(node.right);
            node = queue.poll();
        }
        while (!queue.isEmpty()){
            if (node != null){
                return false;
            }
            node = queue.poll();
        }
        return true;
    }



    //判断两个二叉树是否相等
        //时间复杂度：O(Min(m,n)
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if ((p == null && q != null) || (p != null && q == null)) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    //判断subRoot是否为root的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot){
        if (root == null && subRoot == null) return true;
        if (root == null && subRoot != null) return false;
        if (isSameTree(root, subRoot)) return true;
        if (isSubtree(root.left, subRoot)) return true;
        return (isSubtree(root.right, subRoot));
    }
    //翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    //判断是否为平衡二叉树
        //时间复杂度是n^2
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }
        //时间复杂度是n
    public boolean isBalanced1(TreeNode root) {
        if (root == null) return true;
        return getHeight1(root) >= 0;
    }
    private int getHeight1(TreeNode root){
        if (root == null) return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if (right >= 0 && left >= 0 && Math.abs(left - right) <= 1){
            return Math.max(left, right) + 1;
        }else{
            return -1;
        }
    }
    //判断是否为对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetricChild(root.left,root.right);
    }
    private boolean isSymmetricChild(TreeNode left,TreeNode right){
        if (left == null && right == null) return true;
        if (left != null && right == null || left == null && right != null) return false;
        if (left.val != right.val) return false;
        if (!isSymmetricChild(left.left,right.right)) return false;
        return isSymmetricChild(left.right,right.left);
    }
    //找p和q的公共祖先
        //递归
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (p == root || q == root) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if (left != null && right != null) return root;
        else if (left != null) return left;
        else return right;
    }
        //非递归
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root, p, stack1);
        getPath(root, q, stack2);
        int l = stack1.size() - stack2.size();
        if (l > 0) for (int i = 0 ; i < l; i++) stack1.pop();
        else for (int i = 0 ; i < -l; i++) stack2.pop();
        TreeNode node1 = stack1.pop();
        TreeNode node2 = stack2.pop();
        while(node1 != node2){
            node1 = stack1.pop();
            node2 = stack2.pop();
        }
        return node1;
    }
    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if (root == null) return false;
        stack.push(root);
        if (root == node) return true;
        boolean left = getPath(root.left,node,stack);
        if (left) return left;
        boolean right = getPath(root.right,node,stack);
        if (right) return right;
        stack.pop();
        return false;
    }
    //以前序遍历创建二叉树的字符串(用括号括住每一棵树)
    private StringBuilder str = new StringBuilder();
    public String tree2str(TreeNode root) {
        tree2strChild(root, str);
        return str.toString();
    }
    private void tree2strChild(TreeNode root, StringBuilder str){
        if (root == null) return;
        str.append(root.val);
        if (root.left != null){
            str.append("(");
            tree2strChild(root.left,str);
            str.append(")");
        }else{
            if (root.right != null){
                str.append("()");
            }else{
                return;
            }
        }
        if (root.right != null){
            str.append("(");
            tree2strChild(root.right,str);
            str.append(")");
        }
    }
}
